package com.example.tencentTrain;

import com.example.linked.ListNode;

public class Leetcode21_MergeTwoLists {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(5);
        l1.next.next.next.next = new ListNode(7);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(6);
        l2.next.next.next = new ListNode(7);
        l2.next.next.next.next = new ListNode(9);

        ListNode res = new Solution().mergeTwoLists(l1, l2);

        ListNode tmp = res;
        while (tmp != null) {
            System.out.println(tmp.val);
            tmp = tmp.next;
        }
    }

    static class Solution {
        /**
         * 递归实现
         * @param l1
         * @param l2
         * @return
         */
        private ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
            if (l1 == null)
                return l2;
            else if (l2 == null) return l1;
            else if (l1.val < l2.val) {
                l1.next = mergeTwoLists2(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists2(l1, l2.next);
                return l2;
            }

        }

        /**
         * 方式一：迭代
         *
         * @param l1
         * @param l2
         * @return
         */
        private ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            ListNode res = new ListNode(-1);
            ListNode tmpRes = res;

            // 方式一：从头到尾遍历两个链表
            while (l1 != null || l2 != null) {
                if (l1 != null && l2 != null) {
                    if (l1.val < l2.val) {
                        tmpRes.next = l1;
                        l1 = l1.next;
                    } else {
                        tmpRes.next = l2;
                        l2 = l2.next;
                    }
                } else if (l1 == null) {
                    tmpRes.next = l2;
                    l2 = l2.next;
                } else {
                    tmpRes.next = l1;
                    l1 = l1.next;
                }
                tmpRes = tmpRes.next;
            }


            // 迭代实现二
            // 首先将两个链表都不是null的情况合并
//        while (l1 != null && l2 != null) {
//            if (l1.val < l2.val) {
//                tmpRes.next = l1;
//                l1 = l1.next;
//            } else {
//                tmpRes.next = l2;
//                l2 = l2.next;
//            }
//            tmpRes = tmpRes.next;
//        }
//
//        // 等到一个链表为空后，直接将非空链表插入到结果链表的尾部即可
//        tmpRes.next = l1 == null ? l2 : l1;

            return res.next;
        }

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            return mergeTwoLists1(l1, l2);
        }
    }
}
